import jdk.nashorn.internal.runtime.ListAdapter;

import java.util.HashMap;
import java.util.Map;

public class LinkedListsIntersect {
    /*
    * 链表相交
    * 给你两个单链表的头节点 headA 和 headB ，
    * 请你找出并返回两个单链表相交的起始节点。
    * 如果两个链表没有交点，返回 null 。
    * */
    public static void main(String[] args) {

    }

    // 我的想法是，相交的部分即对象相同，可利用set的不可重复的特性来进行排查(这样一来空间复杂度不满足要求)
    public ListNode mySolution(ListNode headA, ListNode headB){
        Map<ListNode, Integer> map = new HashMap<>();
        // 先把A放进map
        while (headA != null){
            map.put(headA, 0);
            headA = headA.next;
        }
        // 用B来遍历
        while (headB != null){
            Integer integer = map.get(headB);
            if(integer != null)
                return headB;
            headB = headB.next;
        }
        return null;
    }

    // 这俩链长度不是不相等嘛，你就让两个指针从剩余长度相等的地方开始移动不就好了
    // 先找出较长的链，然后移动指针到剩余长度等于短链长度
    public ListNode solution(ListNode headA, ListNode headB){
        // 先计算长度
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null){
            lenA++;
            curA = curA.next;
        }
        while (curB != null){
            lenB++;
            curB = curB.next;
        }
        // 再移动长链指针
        int n = lenA - lenB;
        curA = headA;
        curB = headB;
        if(n >= 0){
            for(int i = 1; i<=n; i++){
                curA = curA.next;
            }
        } else {
            for(int i = 1; i <= (-n); i++){
                curB = curB.next;
            }
        }
        // 开始一起移动
        while (curA != null){
            if(curA==curB)
                return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
